Profile picture

[Java] jgrapht 사용법

Amaranth2023년 05월 21일

jgrapht란?

Graph 자료구조를 지원하는 Java 기반 라이브러리이다.

jgrapht에서 제공하는 기능을 사용해 최단 경로를 도출하거나 가중치의 합을 구할 수 있다.

의존성 추가

gradle.build 파일에 다음 코드를 추가해준다.

dependencies {
		implementation 'org.jgrapht:jgrapht-core:1.0.1'
		...
}

사용법

  • 우테코 지하철 미션의 제공 코드

    @Test
public void getDijkstraShortestPath() {
    WeightedMultigraph<String, DefaultWeightedEdge> graph
            = new WeightedMultigraph(DefaultWeightedEdge.class);
    graph.addVertex("v1");
    graph.addVertex("v2");
    graph.addVertex("v3");
    graph.setEdgeWeight(graph.addEdge("v1", "v2"), 2);
    graph.setEdgeWeight(graph.addEdge("v2", "v3"), 2);
    graph.setEdgeWeight(graph.addEdge("v1", "v3"), 100);

    DijkstraShortestPath dijkstraShortestPath
            = new DijkstraShortestPath(graph);
    List<String> shortestPath
            = dijkstraShortestPath.getPath("v3", "v1").getVertexList();

    assertThat(shortestPath.size()).isEqualTo(3);
}

    위 코드는 다음과 같은 구조의 그래프를 생성하고, v3에서 v1까지의 최단 경로를 도출한다. Untitled Untitled

  • WeightedMultigraph<V, E>(양방향 가중치 그래프) 객체

    • addVertex()로 vertex를 추가해줄 수 있다.

      graph.addVertex("v1");

    • addEdge()로 edge를 추가해줄 수 있다.

      E edge=graph.addEdge("v1", "v2");

    • setEdgeWeight()로 edge의 가중치를 설정해줄 수 있다.

      graph.setEdgeWeight(edge, 2);

이렇게 만든 graph에 dijkstra 알고리즘이 적용된 DijkstraShortestPath 객체를 생성한다.

  • DijkstraShortestPath<V, E> 객체

    • getPath() 메서드를 통해 두 vertex 사이의 최적의 경로 정보를 GraphPath 객체로 받아올 수 있다.

  • GraphPath 객체

    • getWeight()는 해당 경로의 총 가중치를 반환한다.
    • getVertexList()는 해당 경로의 vertex 리스트를 반환한다.

참고 자료

[Java] JGraphT 라이브러리를 통한 최단경로 조회

Loading script...